package com.lqian.simplestructure.recursive;

import com.sun.corba.se.impl.oa.toa.TOA;

/**
 * 汉诺塔问题
 *
 */
public class TestHanoi {
    public static void main(String[] args) {
        hanoi(3,'A','B','C');
    }

    /**
     *
     * @param n  共有n个盘子
     * @param from 开始的柱子
     * @param in 中间的柱子
     * @param to 目标柱子
     */
    public static void hanoi(int n,char from,char in,char to){
        //只有一个盘子 n
        if (n == 1){
            System.out.println("！第1个盘子从"+from+"移到"+to);

        }// 无论有多少个盘子，都认为只有两个。上面的所有盘子和最下面一个盘子
        else{
            //移动A上面n-1所有的盘子到中间位置
            hanoi(n-1,from,to,in);
            //移动盘子
            System.out.println("？第"+n+"个盘子从"+from+"移到"+to);
            //把最上面的所有盘子从中间位置移到目标位置
            hanoi(n-1,in, from,to);
        }

        /**
         * 三次分别包括A堆前（n-1）个移到B堆
         * A堆前（n-1）个移到B堆
         * A堆第n个移动到C堆
         * B堆的(n-1)个移动到C堆
         *
         * 分解（n-1）个盘子的移动需要的次数
         *
         * n=3 3+1+3=7 $ans=2^3-1
         * n=4 7+1+7=15 $ans=2^4-1
         * 同理
         *
         * 将n-1个圆盘从A搬运到B，这时A中只有编号为n的一个圆盘，C中无圆盘；
         * 将A中编号为n的圆盘搬运到C，A无圆盘，C有一个编号为n的圆盘；
         * 回到规模为n-1次的问题，将n-1圆盘从B搬运到C，递归结束。
         */

    }
}
